package third

/*
	给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动k个位置。

	示例 1：
	输入：head = [1,2,3,4,5], k = 2
	输出：[4,5,1,2,3]
	示例 2：
	输入：head = [0,1,2], k = 4
	输出：[2,0,1]

	提示：
	链表中节点的数目在范围 [0, 500] 内
	-100 <= Node.val <= 100
	0 <= k <= 2 * 109

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/rotate-list
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

func rotateRight(head *ListNode, k int) *ListNode {
	if nil == head {
		return nil
	}
	oldHead := head
	fast, slow := head, head
	cur := head
	size := getSize(cur)
	k = k % size
	cur = head
	for cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = oldHead
	for i := 0; i < k; i++ {
		fast = fast.Next
	}
	for fast.Next != oldHead {
		fast = fast.Next
		slow = slow.Next
	}
	newHead := slow.Next
	slow.Next = nil
	return newHead
}

func getSize(cur *ListNode) int {
	size := 0
	for cur != nil {
		size++
		cur = cur.Next
	}
	return size
}
